package excercise.recursive;

import java.util.ArrayList;
import java.util.List;

/**
 * String s = "abcdef"; 全排列
 */
public class Question1_2 {
    public List<String> solution(String str) {
        char[] arr = str.toCharArray();
        List<String> r = new ArrayList<>();
        f(arr, 0, r);

        r.forEach(System.out::println);

        return r;
    }

    public void f(char[] arr, int idx, List<String> r) {

        if (idx == arr.length) {
            StringBuilder s = new StringBuilder();
            for (char c : arr) {
                s.append(c);
            }
            r.add(s.toString());
        }

        for (int i = idx; i < arr.length; i++) {
            if (needSwap(arr, idx, i)) {
                swap(arr, idx, i);
                f(arr, idx + 1, r);
                swap(arr, idx, i);
            }
        }

    }

    public boolean needSwap(char[] arr, int i, int j) {
        // 如果 i ~ j 的范围还存在相同的字符，相当于已经交换过该相同的字符了，不需要再交换了
        for (int k = i; k < j; k++) {
            if (arr[k] == arr[j]) {
                return false;
            }
        }
        return true;
    }

    public void swap(char[] arr, int i, int j) {
        char ch = arr[i];
        arr[i] = arr[j];
        arr[j] = ch;
    }

    public static void main(String[] args) {
        new Question1_2().solution("abcb");
    }
}
